package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 蛇形层次遍历
 * https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
 *
 * @author tzp
 * @since 2020/9/11
 */
public class LC103 implements TreeProblem {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        Deque<TreeNode> current = new ArrayDeque<>();
        Deque<TreeNode> backup = new ArrayDeque<>();
        current.add(root);

        boolean normalDirect = true;//→?

        while (current.size() != 0) {
            TreeNode o = current.removeFirst();
            result.get(result.size() - 1).add(o.val);
            if (normalDirect) {
                if (o.left != null) {
                    backup.addFirst(o.left);
                }
                if (o.right != null) {
                    backup.addFirst(o.right);
                }
            } else {
                if (o.right != null) {
                    backup.addFirst(o.right);
                }
                if (o.left != null) {
                    backup.addFirst(o.left);
                }
            }

            if (current.size() == 0) {//该换行了
                Deque<TreeNode> tmp = current;
                current = backup;
                backup = tmp;

                normalDirect = !normalDirect;
                ArrayList<Integer> a = new ArrayList<>();
                result.add(a);
            }
        }
        result.remove(result.size() - 1);
        return result;
    }

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7);
        TreeNode node15 = new TreeNode(15);
        TreeNode node20 = new TreeNode(20);
        TreeNode node9 = new TreeNode(9);
        TreeNode node3 = new TreeNode(3);
        TreeNode node11 = new TreeNode(11);

        node3.left = node9;
        node3.right = node20;
        node20.left = node15;
        node20.right = node7;

        List<List<Integer>> lists = new LC103().zigzagLevelOrder(node3);
        System.out.println(lists);

        List<List<Integer>> list2 = new LC103().zigzagLevelOrder(node11);
        System.out.println(list2);
    }
}
